/**
 * @Author Fizz Pu
 * @Date 2021/3/6 下午4:20
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

// 子集问题

import  java.util.*;

public class Leeoffer2  {
    public List<List<Integer>> subsets(int[] nums) {

        List<Integer> inner = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        result.add(inner);
        backtrace(result, inner, nums, 0);
        return  result;
    }

    private void backtrace(List<List<Integer>> result, List<Integer> tmp, int[] nums, int start){

        if(start >= nums.length){
            return;
        }

        for(int i = start; i < nums.length; i++){
            tmp.add(nums[i]);
            // 次数使用new
            result.add(new ArrayList<>(tmp));
            // i + 1 不是start + 1
            backtrace(result, tmp, nums, i + 1);
            tmp.remove(tmp.size()-1);
        }
    }
}